#pragma once

#include "Graph.h"
#include <vector>
#include <queue>
#include <stack>

namespace{

	enum colors { WHITE, BLACK, GREY };

	class DefaultUserClass{
	public:
		const void beforeStep(int startVertex) const{}
		const void processEdge(int toVertex, int fromVertex, colors color) const{}

		const void afterCurrentStep(int vertex, int parent) const {}

		const void afterDFS() const{}
	};

	template<class T>
	void DFSStep(const Graph& graph, T* userClass,
		std::stack<int>* vertexStack, std::vector<colors>* vertexColors,
		std::vector<std::vector<int> >* adjacentList,
		std::vector<int>* parentsList, int startVertex = -1) {
		if (startVertex == -1)
			startVertex = vertexStack->top();
		userClass->processEdge(startVertex, -1, WHITE);
		while (!vertexStack->empty()){
			int currentVertex = vertexStack->top();
			if (vertexColors->at(currentVertex) == WHITE){
				adjacentList->at(currentVertex) = graph.getAdjacentList(currentVertex);
				vertexColors->at(currentVertex) = GREY;
			}
			if (adjacentList->at(currentVertex).empty()){
				vertexStack->pop();
				userClass->afterCurrentStep(currentVertex, parentsList->at(currentVertex));
				vertexColors->at(currentVertex) = BLACK;
			}
			else{
				int processColor = adjacentList->at(currentVertex).back();
				if (vertexColors->at(processColor) == WHITE){
					userClass->processEdge(processColor, currentVertex, WHITE);
					vertexStack->push(processColor);
					parentsList->at(processColor) = currentVertex;
				}
				else if (vertexColors->at(processColor) == GREY){
					userClass->processEdge(processColor, currentVertex, GREY);
				}
				else if (vertexColors->at(processColor) == BLACK){
					userClass->processEdge(processColor, currentVertex, BLACK);
				}
				adjacentList->at(currentVertex).pop_back();
			}
		}
	}

	template<class T>
	void DFS(const Graph& graph, T* userClass){
		int numberOfVertexes = graph.getVertexNum();
		std::vector<colors> vertexColors(numberOfVertexes, WHITE);
		std::stack<int> vertexStack;
		std::vector<std::vector<int> > adjacentList(numberOfVertexes);
		std::vector<int> parentsList(numberOfVertexes);
		for (int startVertex = 0; startVertex < numberOfVertexes; ++startVertex){
			if (vertexColors[startVertex] == WHITE){
				userClass->beforeStep(startVertex);
				vertexStack.push(startVertex);
				parentsList[startVertex] = -1; // no parent in DFS tree
				DFSStep(graph, userClass, &vertexStack, &vertexColors,
					&adjacentList, &parentsList);
			}
		}
		userClass->afterDFS();
	}


	template<class T>
	void BFSStep(const Graph& graph, T* userClass,
		std::queue<int>* vertexQueue, std::vector<colors>* vertexColors){
		while (!vertexQueue->empty()){
			int currentVertex = vertexQueue->front();
			vertexQueue->pop();
			vertexColors->at(currentVertex) = GREY;
			std::vector<int> listAdjacents = graph.getAdjacentList(currentVertex);
			for (auto processVertex : listAdjacents){
				if (vertexColors->at(processVertex) == WHITE){
					userClass->processEdge(processVertex, currentVertex, WHITE);
					vertexColors->at(processVertex) = GREY;
					vertexQueue->push(processVertex);
				}
				else if (vertexColors->at(processVertex) == GREY){
					userClass->processEdge(processVertex, currentVertex, GREY);
				}
				else if (vertexColors->at(processVertex) == BLACK){
					userClass->processEdge(processVertex, currentVertex, BLACK);
				}
			}
			vertexColors->at(currentVertex) = BLACK;
		}
	}

	template<class T>
	void BFS(Graph& graph, T* userClass){
		int numberOfVertexes = graph.getVertexNum();
		std::vector<colors> vertexColors(numberOfVertexes, WHITE);
		std::queue<int> vertexQueue;

		for (int startVertex = 0; startVertex < numberOfVertexes; ++startVertex){
			if (vertexColors[startVertex] == WHITE){
				userClass->beforeStep(startVertex);
				vertexQueue.push(startVertex);
				BFSStep(graph, userClass, &vertexQueue, &vertexColors);
			}
		}
		userClass->afterBFS();
	}

	class topologySortClass{
	private:
		std::vector<int> topologySortedArray_;
	public:


		void beforeStep(int vertex){}

		void processEdge(int toVertex, int fromVertex, colors color){
			if (color == GREY)
				throw std::logic_error("Graph contains cycles");
		}

		void afterCurrentStep(int vertex, int parent){
			topologySortedArray_.push_back(vertex);
		}


		void afterDFS(){
			std::reverse(topologySortedArray_.begin(), topologySortedArray_.end());
		}

		std::vector<int> getTopologyOrder(){
			return topologySortedArray_;
		}
	};

	class SimpleBFSClass{
	private:
		std::vector<int> BFSOrder_;
	public:

		void beforeStep(int vertex){
			BFSOrder_.push_back(vertex);
		}

		void processEdge(int toVertex, int fromVertex, colors color){
			if (color == WHITE){
				BFSOrder_.push_back(toVertex);
			}
		}
		void afterCurrentStep(int vertexNum = 0){}


		void afterBFS(){}

		std::vector<int> getBFSOrder(){
			return BFSOrder_;
		}
	};

}

class SimpleDfsClass{
	std::vector<int> onPathVertexes_;
public:
	const void beforeStep(int startVertex) const{
	}


	void processEdge(int toVertex, int fromVertex, colors color){
		if (color == WHITE)
			onPathVertexes_.push_back(toVertex);
	}
	const void afterCurrentStep(int toVertex, int fromVertex) const {}

	const void afterDFS() const {}
	
	const std::vector<int> getDFSOrder() const{
		return onPathVertexes_;
	}
	void clearData(){
		onPathVertexes_.clear();
	}

};


